/**
 平均时间复杂度O(n*n)
 最差情况O(n*n)
 最好情况O(n)
 空间复杂度O(1)
 稳定性：稳定


 基本思路：
 把n个待排序的元素看成为一个有序表和一个无序表。
 开始时有序表只包含一个元素，arr[0]
 无序表中包含n-1个元素，除了arr[0]剩下的全部。

  排序过程中每次从无序表取出第一个元素，把它的排序码依次与有序表的
 元素的排序码进行比较，将它有序地插入到有序表中。
 */



function insertSort(_arr){
    let arr = [..._arr]
    for(let i=1;i<arr.length;i++){
        //待插入的值
        let insertVal = arr[i]
        //待插入的索引
        let insertIndex = i-1
        //找到插入的位置
        //indexIndex >= 0 保证在给 insertVal找插入位置不越界
        //insertVal < arr[insertIndex]表示还没找到插入位置,则把insertVal前面大于insertVal的值逐个后移
        while(insertIndex >= 0 && insertVal < arr[insertIndex]){
            arr[insertIndex + 1] = arr[insertIndex]
            insertIndex--
        }
        //当退出循环说明插入位置找到，
        arr[insertIndex + 1] = insertVal
        console.log(i+'---:'+arr.toString())
    }

}

let array = [5,2,7,4,6,3,1]
insertSort(array)


